/*****************************************************************//**
 * \file   dlist.h
 * \brief  使用Linux内核链表方式实现的双向链表
 * 
 * \author admin
 * \date   August 2022
 *********************************************************************/
#ifndef _DLIST_H_
#define _DLIST_H_


#include "stl_type.h"


//宏定义:


/// <summary>
/// offset_of(struct_type, mem_name)：计算结构体struct_type里的元素mem_name相对结构体的偏移地址。
/// 原理：0被强制转换为struct_type的指针类型，这个struct_type的地址是0，mem_name的地址就是相对0的偏移地址，也是相对结构体的偏移地址。
/// </summary>
//#define offset_of(struct_type, mem_name)  (int)&(((struct_type*)0)->mem_name)


/// <summary>
/// container_of：计算包含节点指针DListNode_ptr的结构体。结构体为struct_type，节点在结构体内的名称是node_in_struct。
/// </summary>
//#define container_of(DListNode_ptr, struct_type, node_in_struct) (struct_type *)((char *)(DListNode_ptr) - offset_of(struct_type,node_in_struct) )


/// <summary>
/// 双向链表结点。参考linux内核的链表，只包含指针域，不包含数据域。
/// </summary>
typedef struct DListNode__
{
	struct DListNode__* prev;
	struct DListNode__* next;
}DListNode;

/// <summary>
/// 双向链表结构体。
/// </summary>
typedef struct  DList__
{
	/// <summary>
	/// 链表节点数量。
	/// </summary>
	int count; 
	/// <summary>
	/// 链表的比较函数。key1>key2返回1，key1<key2返回-1,key1=key2返回0.
	/// </summary>
	int (*match)(DListNode* key1, DListNode* key2); 

	/// <summary>
	/// 如果是按序插入，就是从小往大排列，头节点是最小的节点。
	/// </summary>
	DListNode* head;  
	/// <summary>
	/// 如果是按序插入，就是从小往大排列，尾节点是最大的节点。
	/// </summary>
	DListNode* tail;   
}DList;





/// <summary>
/// 初始化链表
/// </summary>
/// <param name="list">链表结构体</param>
/// <param name="c">链表节点的比较函数。在有序插入的时候要用到。</param>
void dlist_init(DList* list, int (*c)(DListNode*, DListNode*));

/// <summary>
/// 销毁双向链表。链表只记录头尾节点信息，不记录数据，所以只初始化头尾节点即可
/// </summary>
/// <param name="list">链表结构体</param>
void dlist_destroy(DList* list);


/// <summary>
/// 按照索引查找节点
/// </summary>
/// <param name="list">链表</param>
/// <param name="index">链表从头开始的索引</param>
/// <returns>节点指针，如果索引超出范围，返回null</returns>
DListNode* dlist_index(DList* list, int index);


/// <summary>
/// 查找节点的索引
/// </summary>
/// <param name="list">链表</param>
/// <param name="node">节点</param>
/// <returns>节点的索引，索引从0开始计数，如果节点不在链表上，返回-1</returns>
int dlist_index_of(DList* list, DListNode* node);

/// <summary>
/// 在 element 后面插入一个新元素
/// </summary>
/// <param name="list">链表结构体</param>
/// <param name="element">定位的节点</param>
/// <param name="new_element">新插入的节点</param>
/// <returns>是否插入成功，如果element是合法的节点，是可以成功插入的</returns>
bool dlist_ins_next(DList* list, DListNode* element, DListNode* new_element);

/// <summary>
/// 在 element 前面插入一个新元素
/// </summary>
/// <param name="list">链表结构体</param>
/// <param name="element">定位的节点</param>
/// <param name="new_element">新插入的节点</param>
/// <returns>是否插入成功，如果element是合法的节点，是可以成功插入的</returns>
bool dlist_ins_prev(DList* list, DListNode* element, DListNode* new_element);

/// <summary>
/// 在双向链表 中移除 element 元素
/// </summary>
/// <param name="list">链表结构体</param>
/// <param name="element">移除的节点</param>
/// <returns>是否操作成功。如果element是合法的节点，是可以操作成功的</returns>
bool dlist_remove(DList* list, DListNode* element);

/// <summary>
/// 在双向链表尾部插入一个元素。
/// </summary>
/// <param name="list">链表结构体</param>
/// <param name="new_element">新插入的节点</param>
/// <returns>是否操作成功</returns>
bool dlist_push_back(DList* list, DListNode* new_element);

/// <summary>
/// 在双向链表头部插入一个元素。
/// </summary>
/// <param name="list">链表结构体</param>
/// <param name="new_element">新插入的节点</param>
/// <returns>是否操作成功</returns>
bool dlist_push_front(DList* list, DListNode* new_element);

/// <summary>
/// 在双向链表尾部弹出一个数据
/// </summary>
/// <param name="list">链表结构体</param>
/// <returns>是否操作成功</returns>
bool dlist_pop_back(DList* list);

/// <summary>
/// 在双向链表头部弹出一个数据
/// </summary>
/// <param name="list">链表结构体</param>
/// <returns>是否操作成功</returns>
bool dlist_pop_front(DList* list);


/// <summary>
/// 按序插入节点。按照从小到大的顺序插入。如果所有元素都是按序插入的，整个链表就是有序的。
/// </summary>
/// <param name="list">链表结构体</param>
/// <param name="new_element">新插入的节点</param>
/// <returns>是否操作成功</returns>
bool dlist_ins_orderly(DList* list, DListNode* new_element);


//


void test_dlist(void);



#endif

//

